//n个骰子的点数
class Solution {
public:
    vector<double> dicesProbability(int n)
    {
        //times[i][j] 为i个骰子 点数和为j的次数
        
        //times[i][j] = times[i - 1][j - 1] + times[i - 1][j - 2] 
        //                      + ... + times[i - 1][j - 6]
        vector<vector<int>> times(n + 1, vector<int>(6 * n + 1, 0));
        // 初始化
        for (int i = 1; i <= 6; i++)
         {
            times[1][i] = 1;
        }
        // 有几个骰子
        for (int i = 2; i <= n; i++) 
        {
            //骰子可以掷出来的大小范围  两个骰子就是 2-12
            for (int j = i; j <= 6 * i; j++) 
            {
                //每一个骰子扔出来的值在1-6之间
                for (int k = 1; k <= 6; k++) 
                {
                    if (k > j) break;
                    times[i][j] =times[i][j]+times[i - 1][j - k];
                }
            }
        }
        // 计算概率
        double total = 1.0 * pow(6, n);
        vector<double> probs;
        for (int j = n; j <= 6 * n; j++) 
        {
            probs.push_back(times[n][j] / total);
        }
        return probs;
    }
};
//机器人的运动范围
class Solution {
public:
    int movingCount(int m, int n, int k) 
    {
        vector<vector<int>>map(m,vector<int>(n,0));
        dfs(map,m,n,0,0,k);
        int res=0;
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(map[i][j]==1) res++;
            }
        }
        return res;
    }
    int arr[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
    bool check(int x,int y,int k)
    {
        int count=0;
        while(x>0)
        {
            count+=x%10;
            x/=10;
        }
        while(y>0)
        {
            count+=y%10;
            y/=10;
        }
        if(count > k) return false;
        else return true;
    }
    void dfs(vector<vector<int>>& map,int m,int n,int curx,int cury,int k)
    {
        map[curx][cury]=1;
        for(int i=0;i<4;i++)
        {
            int nx=curx+arr[i][0];
            int ny=cury+arr[i][1];
            if(nx <0 | nx>=m || ny<0 || ny>=n  || map[nx][ny]==1) continue;
            if(check(nx,ny,k))
            {
                dfs(map,m,n,nx,ny,k);
            }
        }
    }
};
//最少的硬币数目
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) 
    {
        //dp[i] 组成金额为i的最少硬币数
        vector<int>dp(amount+1,INT_MAX);
        dp[0]=0;
        for(int i=0;i<coins.size();i++)
        {
            for(int j=coins[i];j<=amount;j++)
            {
                if(dp[j-coins[i]]!=INT_MAX)
                {
                    dp[j]=min(dp[j-coins[i]]+1,dp[j]);
                }
            }
        }
        if(dp[amount]==INT_MAX) return -1;
        return dp[amount];
    }
};